package com.javase;

public class recursion01 {
    //编写一个main方法
    public static void main(String[] args) {
        //新建T对象
        T t = new T();
        System.out.println("当n=8时，对应的斐波那契数是："+t.fib(7));
        //猴子吃桃调用方法
        int day = 1;
        int res = t.monkey(day);
        System.out.println("第"+day+"天有"+res+"个桃子。");
        //迷宫问题
        //先创建一个迷宫（二维数组）
        int[][] map = new int[8][7];
        //规定map数组元素 0 表示路 1 表示障碍物
        for (int i = 0;i < 7;i++){
            map[0][i] = 1;
            map[7][i] = 1;
            map[i][0] = 1;
            map[i][6] = 1;
        }
        map[3][1] = 1;
        map[3][2] = 1;
        map[3][5] = 1;
        map[3][4] = 1;
        map[5][4] = 1;
        map[5][5] = 1;
        map[6][2] = 1;
//        for (int i = 0;i < map.length;i++){
//            map[i][0] = 1;
//            map[i][6] = 1;
//        }
        //输出二维数组
        for (int[] ints : map) {
            for (int anInt : ints) {
                System.out.print(anInt);
            }
            System.out.println();
        }
        //使用方法找路
        t.findWay(map,1,1);
        System.out.println("=============找路情况===============");
        for (int[] ints : map){
            for (int arr : ints){
                System.out.print(arr+" ");
            }
            System.out.println();
        }
    }
}

class T{
    //斐波那契数列
    public int fib(int n){
        if (n>=1) {
            if (n == 1 || n == 2) {
                return 1;
            } else {
                return fib(n - 1) + fib(n - 2);
            }
        }
        return 0;
    }
    //猴子吃桃
    public int monkey(int n){
        if (n == 10){
            return 1;
        }else {
            return (monkey(n + 1) + 1) * 2;
        }
    }
    //找出迷宫路径，如果找到返回true否则返回false
    //初始位置下标为map[1][1]
    //数组中0表示路，1表示障碍物，2表示可以走的路径，3表示走过的路径但走不通
    //当map[6][5] = 2 说明找到通路，可以结束，否则就继续找
    //确定找路策略 右→下→左→上
    public boolean findWay(int[][] map,int i,int j){
        if (map[6][5] == 2){//已经找到出口，结束递归
            return true;
        }else {
            if (map[i][j] == 0){//说明当前位置是0，可以走
                //假设可以走通
                map[i][j] = 2;
                //使用找路策略确定是否走通
                if (findWay(map,i,j-1)){//左
                    return true;
                }else if (findWay(map,i+1,j)){//下
                    return true;
                }else if (findWay(map,i,j+1)){//右
                    return true;
                }else if (findWay(map,i-1,j)){//上
                    return true;
                }else {
                    map[i][j] = 3;
                    return false;
                }

            }else {
                return false;
            }
        }
    }
}